package com.dyz.leetcode;

import java.util.ArrayList;
import java.util.List;

public class Permute46 {
    public static void main(String[] args) {
        int [] nums = {1,2,3};
        List<List<Integer>> permute = new Permute46().permute(nums);
        System.out.println(permute);
    }
    private List<List<Integer>> res;
    public List<List<Integer>> permute(int[] nums) {
        //回溯
        res = new ArrayList<>();
        if(nums==null || nums.length==0){return res;}
        //回溯使用的是否已经添加
        boolean[] used = new boolean[nums.length];
        List<Integer> list = new ArrayList<>();
        helper(list, nums, 0, used);
        return res;
    }
    private  void helper(List<Integer> list, int[] nums, int index, boolean[] used){
        //终止条件
        if(index==nums.length){
            res.add(new ArrayList<>(list));
            return;
        }
        //遍历
        for (int i=0; i<nums.length; i++){
            if(!used[i]) {
                list.add(nums[i]);
                used[i] = true;
                helper(list, nums, index + 1, used);
                used[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
}
